package leetcode.interview;

public class Solution10_03 {
    public int search(int[] arr, int target) {
        //多次旋转跟一次旋转性质一样，就当成一次旋转即可
        int l = 0, r = arr.length-1, mid = 0;
        while (l<=r){
            if(arr[l]==target) return l; //l是目前最小的索引
            mid = (l+r)>>1;
            if(arr[mid]==target){//不能立即返回，要找到最小的那个下标，让右边界收缩
                r = mid;
                continue;
            }
            if(arr[mid]>arr[r]){ //mid在左支，[l,mid]有序
                if(target>arr[l]&&target<arr[mid]){ //target在有序区间[l,mid]内
                    r = mid-1;
                }else{ //target不在[l,mid]
                    l = mid+1;
                }
            }else if(arr[mid]<arr[r]){ //mid在右支，[mid,r]有序
                if(target>arr[mid]&&target<=arr[r]){ //target在有序区间[mid,r]内
                    l = mid+1;
                }else{ //target不在[mid,r]
                    r = mid-1;
                }
            }else { //nums[mid]==nums[r]
                // 无法直接让l=mid+1或r=mid-1，因为这样可能漏掉一些没搜索到的num
                // 但已知nums[r]!=target，所以可以收缩右边界一步
                r = r - 1;
            }
        }
        return -1;
    }
}
